# -*- coding: utf-8 -*-

'''
@author: Soraia Janeiro 6051
@author: Lenia Andrade 5607
@date: Junho 2013
@summary: Este modulo contem a classe Algorithm_library
'''

import math

class Algorithm_library:
	'''
    @summary: Esta classe define os algoritmos.
    '''
	
	def insertionSort(self, A):
		
		'''
		@summary: O metodo efectua a ordenação de uma lista.
		@param A: é uma lista de valores aleatórios.
		@return: A, retorna a lista A ordenada.
		'''
		
		for j in range(0, len(A)):
			key = A[j]
			i = j - 1
			while(i > -1 and A[i] > key):
				A[i + 1] = A[i]
				i = i - 1
				pass
			A[i + 1] = key
			pass
		return A
        
	def bubbleSort(self, A):
		
		'''
		@summary: O metodo realiza a ordenação de uma lista, não ordenada, passada por parametro..
		@param A: é uma lista de valores aleatórios.
		@return: A, retorna a lista A ordenada.
		'''
		
		for i in xrange (0, len(A)):
			for j in xrange (len(A) - 1, i, -1):
				if A[j] < A[j - 1]:
					A[j], A[j - 1] = A[j - 1], A[j]
					pass
				pass
			pass
		return A
		
	
	def max_heapify(self, A, i, heapsize):
		
		'''
		@summary: O metodo analisa se o valores do nó pai, é sempre superior ao valor dos nós filhos. Efectua trocas quando necessario.
		@param A: Lista de valores aleatórios.
		@param i: Um indice da tabela.
		@param heapsize: Numero de elementos da lista
		'''
		
		l = 2 * i + 1
		r = 2 * i + 2
		
		if l <= heapsize and A[l] > A[i]:
			largest = l
			pass
		
		else:
			largest = i
			pass
		
		if r <= heapsize and A[r] > A[largest]:
			largest = r
			pass
		
		if largest != i:
			A[i], A[largest] = A[largest], A[i]
			self.max_heapify(A, largest, heapsize)
			pass
		pass
	
	
	
	def build_max_heap(self, A, heapsize):
		
		'''
		@summary: O metodo ordena a heap.
		@param A: Lista de valores aleatórios.
		@param heapsize: Numero de elementos da lista
		'''
		
		i = int(math.floor((len(A) - 1) / 2.0))
		for i in range(int(math.floor((len(A) - 1) / 2.0)), 0, -1):
			self.max_heapify(A, i, heapsize)
			pass
		pass
		
	
	def heapsort(self,A):
		
		'''
		@summary: O metodo coloca os elementos ordenados.
		@param A: Lista de valores aleatórios.
		@return: A, retorna a lista A ordenada.
		'''
		
		heapsize = len(A)-1
		self.build_max_heap(A,heapsize)
		i = len(A)-1
		
		while i > 0:
			self.max_heapify(A, 0, heapsize)
			A[0], A[i] = A[i], A[0]
			heapsize = heapsize - 1
			self.max_heapify(A, 0, heapsize)
			i = i - 1
			pass
		return A
	
	
	def merge(self,A, p, q, r):
		
		'''
		@summary: O metodo divide a lista em duas sub-listas, e efectua a ordenação em relação ao pivô.
		@param A: é uma lista de valores aleatórios.
		@param p: é um índice da tabela, a primeira posição.
		@param q: é um índice da tabela, o pivô.
		@param r: é um índice da tabela, a ultima posição.			
		@return: A, retorna a lista A.
		'''
		
		L = list()
		R = list()
		n1 = q - p + 1
		#print n1
		n2 = r - q
		#print n2
		for i in range (0, n1):
			L.append(A[p + i])
			pass
		for j in range (0, n2):
			R.append(A[q + j + 1])
			pass
		L.append(999999999999999999999999)
		R.append(999999999999999999999999)
		#print "L = ", L
		#print "R = ", R
		i = 0
		j = 0
		
		for k in range(p, (r + 1)):
			if (L[i] <= R[j]):
				A[k] = L[i]
				i += 1
				pass
			else:
				A[k] = R[j]
				j = j + 1
				pass
			pass
		return A
	

	def mergeSort(self,A, p, r):
		
		'''
		@summary: O metodo junta as sub-listas.
		@param A: é uma lista de valores aleatórios.
		@param p: é um índice da tabela, a primeira posição.
		@param r: é um índice da tabela, a ultima posição.			
		@return: A, retorna a lista A ordenada.
		'''
		
		if p < r:
			q = int(math.floor((p + r)/2.0))
			A = self.mergeSort(A, p, q)
			A = self.mergeSort(A, q + 1, r)
			A = self.merge(A, p, q, r)
		return A
		
	
	def partition(self, A, p, r):
		
		'''
		@summary: O metodo divide a tabela em duas sub-tabelas..
		@param A: é uma lista de valores aleatórios.
		@param p: é um índice da tabela, a primeira posição.
		@param r: é um índice da tabela, a ultima posição.
		@return: i + 1.
		'''
		x = A[r]
		i = p - 1
		
		for j in range (p, r):
			if A[j] <= x:
				i = i + 1
				A[i], A[j] = A[j], A[i]
				pass
			pass
		A[i + 1], A[r] = A[r], A[i + 1]
		return i + 1
	
	def quicksort(self,A, p, r):
		
		'''
		@summary: O metodo realiza a ordenação das sub-tabelas.
		@param A: é uma lista de valores aleatórios.
		@param p: é um índice da tabela, a primeira posição.
		@param r: é um índice da tabela, a ultima posição.
		@return: A, retorna a tabela A ordenada.
		'''
		
		if p < r:
			q = self.partition(A, p, r)
			self.quicksort(A, p, q - 1)
			self.quicksort(A, q + 1, r)
			pass
		return A
	
	
